#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int weight;
    int parent;
    int lchild;
    int rchild;
} TreeNode;

typedef struct HFTree {
    TreeNode *data;
    int length;
} HFTree; 

HFTree *initTree(int *weight, int length)
{
    HFTree *T = (HFTree *)malloc(sizeof(HFTree));//分配哈夫曼树空间
    T->data = (TreeNode *)malloc(sizeof(TreeNode) * (2 * length -1)); //整合之后是2*n-1个节点
    T->length = length;
    for (int i = 0; i < length; i++) {
        T->data[i].weight = weight[i];
        T->data[i].parent = 0; //往后取值length - 2*length-1
        T->data[i].lchild = -1;
        T->data[i].rchild = -1;
    }
    return T;
}

int * selectMin(HFTree *T) //最小值res[0] 第二小值res[1] 下标值
{
    int Min = 10000;
    int secondMin = 10000;
    int MinIndex;
    int secondIndex;
    //寻找最小值
    for (int i = 0; i < T->length; i++) {
        if (T->data[i].parent == 0) {
            if (T->data[i].weight < Min) {
                Min = T->data[i].weight;
                MinIndex = i;
            }
        }
    }
    //寻找第二小值
    for (int i = 0; i < T->length; i++) {
        if (T->data[i].parent == 0) {
            if (T->data[i].weight < secondMin && i != MinIndex) {
                secondMin = T->data[i].weight;
                secondIndex = i;
            }
        }
    }
    //返回这两个值
    int *res = (int *)malloc(sizeof(int) * 2);
    res[0] = MinIndex;
    res[1] = secondIndex;
    return res;
}

void preOrder(HFTree *T, int index) 
{
    if (index != -1) {//初始化时叶子结点初始化一
        printf("%d ", T->data[index].weight);
        preOrder(T, T->data[index].lchild);
        preOrder(T, T->data[index].rchild);
    }
}

void createTree(HFTree *T) 
{   //一些变量
    int *res;
    int Min;
    int secondMin;
    int loopLength = 2 * T->length -1;
    for (int i = T->length; i < loopLength; i++) {
        res = selectMin(T);
        Min = res[0];
        secondMin = res[1];
        T->data[i].weight = T->data[Min].weight + T->data[secondMin].weight;
        //赋值父母
        T->data[Min].parent = i;
        T->data[secondMin].parent = i;
        T->data[i].parent = 0;//别忘记了
        //赋值孩子
        T->data[i].lchild = Min;
        T->data[i].rchild = secondMin;
        T->length++; //init后是length然后++
    }
}

int main(void)
{
    int weight[7] = {5,1,3,6,11,2,4};
    HFTree *T = initTree(weight, 7);
    createTree(T);
    preOrder(T, T->length-1);

    return 0;
}
 